package com.example.arithmeticleetcode.learnArithmetic2.graph;

import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-11-17 10:59
 **/
public class Main {

    static Graph.WeightManager<Double> weightManager = new Graph.WeightManager<Double>() {
        @Override
        public int compare(Double w1, Double w2) {
            return w1.compareTo(w2);
        }

        @Override
        public Double add(Double w1, Double w2) {
            return w1 + w2;
        }

        @Override
        public Double zero() {
            return 0.0;
        }
    };

    public static void main(String[] args) {
//        testBfs();
//        testDfs();
//        testTop();
        testMultiSp();
    }

    static void testMultiSp() {
        Graph<Object, Double> graph = directedGraph(Data.NEGATIVE_WEIGHT1);
        Map<Object, Map<Object, Graph.PathInfo<Object, Double>>> shortestPath = graph.shortestPath();
        shortestPath.forEach((from, path) -> {
            System.out.println(from + "------------------------");
            path.forEach((to, pathInfo) -> {
                System.out.println(to + " - " + pathInfo);
            });
        });
    }

    static void testSp() {
        Graph<Object, Double> graph = undirectedGraph(Data.SP);
        Map<Object, Graph.PathInfo<Object, Double>> sp = graph.shortesPath("A");
        if (sp == null) return;
        sp.forEach((v, path) -> {
            System.out.println(v + " - " + path);
        });
    }

    static void testMst() {
        Graph<Object, Double> graph = undirectedGraph(Data.MST_01);
        Set<Graph.EdgeInfo<Object, Double>> edgeInfos = graph.mst();
        for (Graph.EdgeInfo<Object, Double> edgeInfo : edgeInfos) {
            System.out.println(edgeInfo);
        }
    }

    static void testTop() {
        Graph<Object, Double> graph = directedGraph(Data.TOPO);
        List<Object> list = graph.topologicalSort();
        System.out.println(list);
    }

    private static void testDfs() {
//        Graph<Object, Double> graph = directedGraph(Data.DFS_02);
//        graph.dfs("c");
    }

    private static void testBfs() {
        Graph<Object, Double> graph = directedGraph(Data.BFS_02);
        graph.bfs(0, v -> {
            System.out.println(v);
            return false;
        });
    }

    private static void test02() {
        ListGraph<String, Integer> graph = new ListGraph();
        graph.addEdge("v0", "v1");
        graph.addEdge("v1", "v0");

        graph.addEdge("v0", "v2");
        graph.addEdge("v2", "v0");

        graph.addEdge("v0", "v3");
        graph.addEdge("v3", "v0");

        graph.addEdge("v2", "v1");
        graph.addEdge("v1", "v2");

        graph.addEdge("v2", "v3");
        graph.addEdge("v3", "v2");

        graph.print();
    }

    private static void test01() {
//        ListGraph<String, Integer> graph = new ListGraph();
//        graph.addEdge("v1", "v0", 9);
//        graph.addEdge("v1", "v2", 3);
//        graph.addEdge("v2", "v0", 2);
//        graph.addEdge("v2", "v3", 5);
//        graph.addEdge("v3", "v4", 1);
//        graph.addEdge("v0", "v4", 6);

//        graph.bfs("v1");
//
//        graph.print();
//        graph.removeEdge("v0", "v4");
//        System.out.println("=======");
//        graph.removeVertext("v0");
//        graph.print();
    }

    /**
     * 有向图
     */
    private static Graph<Object, Double> directedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertext(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
            }
        }
        return graph;
    }

    /**
     * 无向图
     *
     * @param data
     * @return
     */
    private static Graph<Object, Double> undirectedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>(weightManager);
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertext(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
                graph.addEdge(edge[1], edge[0]);
            } else if (edge.length == 3) {
                double weight = Double.parseDouble(edge[2].toString());
                graph.addEdge(edge[0], edge[1], weight);
                graph.addEdge(edge[1], edge[0], weight);
            }
        }
        return graph;
    }
}
